Simulation has many applications. It is used to design and prototype products. It is used to engineer and test materials and designs. It is used for training and education. It is used to create content for various forms of entertainment, animation, and virtual reality. It is also used in medicine; medical simulators include those used for making diagnostics of diseases and medical conditions, and for simulating surgery and surgical techniques. It is used in robotics. And simulation is used for many other purposes.
Simulation affords users the benefits of experience without the risk. Simulation can also be used to more effectively train users by increasing the number and variety of situations with which they come into contact. Simulation also allows research and exploration in new and meaningful ways. Users can repeat a given process many times to determine a best approach, each time trying a different method.
The practice of simulation is usually categorized by methodology. The most popular methods are rigid-body simulation, flexible-body simulation, and finite element analysis.
Rigid-body simulation is the practice of simulating an object using a group of point-masses, each point-mass having an unchanging distance from the other point-masses in the group. The entire group can be represented by a single position—the position of the group's center-of-mass—and a single orientation. Rigid bodies can be connected to each other by constraints or forces. The motion of a rigid body is described by changes in its center-of-mass position and its orientation.
Flexible-body simulation (or spring and dashpot simulation) is the practice of simulating an object using individual point-masses connected by idealized springs. Each spring has associated parameters, and applies equal-and-opposite forces to the masses at each of its ends. The spring attempts to maintain a specified distance between its masses. The motion of a flexible body is described by changes in the positions of each of the body's point-masses.
Finite element analysis (or FEA) is the practice of simulating an object using similarly shaped elements. A finite element model (or FEM) is composed of volumetric elements, such as tetrahedra, each having associated parameters and equations of motion. A group of elements and their parameters are used to describe a system of equations to be solved. The motion of a finite element model is described by the deformations of its elements.
In an interactive simulation, object positions are computed and displayed many times per second to give the appearance of motion. The term frame-rate is defined as the number of times per second the objects are displayed.
A limitation of rigid-body simulations is that they do not allow the simulation of soft objects. They are restricted to rigid objects and rigid or flexible links between these objects.
A limitation of flexible-body simulations is that they have difficulty simulating rigid or semi-rigid objects. As springs are made stiffer, instabilities arise, and their equations become increasingly difficult to solve at interactive frame-rates.
Another limitation of flexible-body simulations is that they simulate rotations by propagating translations across a network of springs. This makes the rotation of a body dependent upon the spring network and the number of steps used to advance the simulation in time. The fewer the number of springs, and the more steps used, the faster the apparent rotation occurs.
A limitation of FEA simulations is that they do not allow interaction with simulated objects, due to the time required for computation. Allowing interaction with simulated objects is desirable in that it provides modalities for approaching tasks in the industries that use simulators, and might allow simulators to be used in new industries.
Another limitation of FEA is the requirement that FEM objects be composed of homogeneously-shaped elements, which makes their creation more difficult, error-prone, and in certain situations, impossible. A more desirable method is an unstructured approach, whereby objects may be made any shape, dimension, or topology.
There are newer simulation technologies which allow for interaction with soft objects. One limitation of some of these technologies is the necessity to precompute certain aspects of the model's response to forces, or to make certain variables unchangeable. This makes it difficult to generate objects, or to change the characteristics of existing objects, while the simulation is running.
Another limitation of certain newer interactive soft-body simulation technologies is their inability to simulate materials that respond to forces in a nonlinear manner. Each object must be made of material or elements whose force-response is linear in nature.
Another limitation of certain newer interactive soft-body simulation technologies is the necessity that objects or elements be composed of homogeneous materials. This does not allow objects composed of heterogeneous materials to be simulated efficiently.
Another limitation of some soft-body technologies is the necessity that objects be made up of incompressible elements, which limits the kinds of materials that can be simulated.
Yet another limitation of some soft-body simulation technologies is an inability to simulate materials that are not in equilibrium. This precludes simulating objects with active, dynamic properties, such as those that change shape when stimulated by an electrical current.
There are a number of other problems specifically associated with interactive material simulations. Research has typically been done in the component areas of collision detection, collision response, rigid-body simulation, and flexible-body simulation. Barriers to a general-purpose interactive material simulation have historically included:                The amount of data to be computed in order to achieve a reasonable simulation        The complexity and number of calculations necessary        Lack of appropriate numerical methods to bring to bear on the simulation        Lack of methods to calculate real-time collisions between irregular moving surfaces        Lack of expertise in the calculation of forces between colliding flexible bodies        The inability to derive solutions to the motions of complicated dynamic models at interactive rates.        
There have been attempts to solve some of these problems. For example, U.S. Pat. No. 7,050,955, entitled “System, method and data structure for simulated interaction with graphical objects,” that issued to Carmel et al., teaches “Object simulation and interaction of and between computer-generated or graphical objects in a virtual space includes neutral scene graphs, data structures and procedures for using such graphs and data structures.
U.S. Pat. No. 6,714,901, entitled “Electronic device for processing image-data, for simulating the behaviour of a deformable object,” that issued to Cotin et al. teaches “An electronic device for processing image data, particularly image data pertaining to medical procedures, includes a user interface with force feedback (4) corresponding to tool reactions, a “collision” module (18) for estimating a point of intersection between a straight line embodying a displacement derived from the action of the tool and a surface mesh of a given object, and an internal forces module (16) which estimates internal forces exerted on nodes of a first part of at least a volume mesh of the object, on the basis of a displacement applied on nodes pertaining to the surface mesh containing a point of intersection, of boundary conditions, and of node tensors and link tensors, from matrices of rigidity, and a reaction module (20) for determining the reaction force of the object corresponding to its deformation estimated on the basis of the internal forces, such that the force generated by the user interface (4) is balanced by reaction force.”
U.S. Pat. No. 6,560,658, entitled “Data storage device with quick and quiet modes,” that issued to Singer et al. teaches “Techniques are provided herein for reducing vibrations in various modes of a dynamic system. One such technique comprises incorporating vibration limiting and sensitivity constraints into a partial fraction expansion equation model of the system so as to reduce vibrations to specific levels. Another technique comprises shaping a command determined using the partial fraction expansion equation model to produce a desired output. The entire command may be shaped or only selected portions thereof which produce vibrations. Another technique involves commanding in current to produce saturation in voltage. By doing this, it is possible to command voltage switches. The times at which the switches occur can be set to reduce system vibrations. Other techniques are also provided. These include varying transient portions at the beginning, middle and/or end of a move and using Posicast inputs, among others.”
U.S. Pat. No. 6,486,872, entitled “Method and apparatus for providing passive fluid force feedback,” that issued to Rosenberg teaches “A method and apparatus for interfacing the motion of an object with a digital processing system includes a sensor for detecting movement of the object along a degree of freedom. A passive pneumatic or hydraulic damper is coupled to the object to provide a damping resistance to the object along the degree of freedom and resist a movement of the object. The damping resistance is provided by regulating the control of a fluid with a digital computing apparatus, thus providing a low-cost, low-power force-feedback interface that is safe for the user. The damper and sensor provide an electromechanical interface between the object and the electrical system. A gimbal or other interface mechanism can be coupled between the damper and the object. The interface is well suited for simulations or video games in which an object such as a joystick is moved and manipulated by the user.”
U.S. Pat. No. 6,314,473, entitled “System for removing selected unwanted frequencies in accordance with altered settings in a user interface of a data storage device,” that issued to Singer et al., teaches “Techniques are provided herein for reducing vibrations in various modes of a dynamic system. One such technique comprises incorporating vibration limiting and sensitivity constraints into a partial fraction expansion equation model of the system so as to reduce vibrations to specific levels. Another technique comprises shaping a command determined using the partial fraction expansion equation model to produce a desired output. The entire command may be shaped or only selected portions thereof which produce vibrations. Another technique involves commanding in current to produce saturation in voltage. By doing this, it is possible to command voltage switches. The times at which the switches occur can be set to reduce system vibrations. Other techniques are also provided. These include varying transient portions at the beginning, middle and/or end of a move and using Posicast inputs, among others.”
U.S. Pat. No. 6,300,937, entitled “Method and apparatus for controlling force feedback for a computer interface device,” that issued to Rosenberg teaches “A method and apparatus for controlling and providing force feedback using an interface device manipulated by a user. A microprocessor is provided local to the interface device and reads sensor data from sensors that describes the position and/or other information about an object grasped and moved by the user, such as a joystick. The microprocessor provides the sensor data to a host computer that is coupled to the interface device by a communication bus that preferably includes a serial interface. In a “host-controlled” embodiment, the host computer calculates force values using the sensor data and other parameters of a host application program and sends the force values to the local microprocessor, which directly provides the force values to actuators to apply forces to the user object. In a “reflex” embodiment, the host computer sends high level supervisory commands to the local microprocessor, and the microprocessor independently implements a local process based on the high level command for reading sensor data and providing force values to the actuators using sensor data and other parameters.”
U.S. Pat. No. 6,211,848, entitled “Dynamic holographic video with haptic interaction,” that issued to Plesniak et al., teaches “A user is able to interact with and modify an electronic holographic image using a force-feedback (or haptic) device, which is capable of sensing and reporting the 3D position of its hand-held stylus and “displaying” appropriate forces to the user. Thus, a user can feel and modify specified shapes in the haptic workspace. The haptic workspace is precisely registered with the free-standing, spatial image displayed by a holographic video (holovideo) system. In the coincident visuo-haptic workspace, a user can see, feel, and interact with synthetic objects that exhibit many of the properties one expects of real ones, and the spatial display enables synthetic objects to become a part of the user's manipulatory space.”
U.S. Pat. No. 6,113,395, entitled “Selectable instruments with homing devices for haptic virtual reality medical simulation,” that issued to Hon teaches “Invention is apparatus for using selectable instruments in virtual medical simulations with input devices actuated by user and resembling medical instruments which transmit various identifying data to the virtual computer model from said instruments which have been selected; then, said apparatus assist in creating full immersion for the user in the virtual reality model by tracking and homing to instruments with haptic, or force feedback generating, receptacles with which said instruments dock by means of a numerical grid, creating a seamless interface of instrument selection and use in the virtual reality anatomy.”
U.S. Pat. No. 5,882,206, entitled “Virtual surgery system,” that issued to Gillio teaches “A virtual surgery system or virtual testing system provides a simulation or test based on image data. A simulator combined with a real exam requires simulation tasks by a test taker. Additionally, a surgical procedure may be simulated using image data of a patient in devices simulating the physical instruments a surgeon uses in performing the actual procedure, for example. The user input device, such as a mouse, three dimensional mouse, joystick, seven dimensional joystick, full size simulator, etc., can be used in a virtual simulation to move through the image data while the user looks at the data and interaction of the input device with the image data on a display screen. Force feedback can be provided based on physical constraint models (of the anatomy, for example), or based on edge and collision detection between the virtual scope or virtual tool used by the operator and walls or edges of the image data in the image space. The virtual simulator may be used as a teaching, training, testing, demonstration, or remote telesurgery device, for example.
U.S. Pat. No. 5,704,791, entitled “Virtual surgery system instrument,” that issued to Gillio teaches “A virtual surgery system or virtual testing system provides a simulation or test based on image data. A simulator combined with a real exam requires simulation tasks by a test taker. Additionally, a surgical procedure may be simulated using image data of a patient in devices simulating the physical instruments a surgeon uses in performing the actual procedure, for example. The user input device, such as a mouse, three dimensional mouse, joystick, seven dimensional joystick, full size simulator, etc., can be used in a virtual simulation to move through the image data while the user looks at the data and interaction of the input device with the image data on a display screen. Force feedback can be provided based on physical constraint models (of the anatomy, for example), or based on edge and collision detection between the virtual scope or virtual tool used by the operator and walls or edges of the image data in the image space. The virtual simulator may be used as a teaching, training, testing, demonstration, or remote telesurgery device, for example.”
U.S. Pat. No. 5,739,811, entitled “Method and apparatus for controlling human-computer interface systems providing force feedback,” that issued to Rosenberg teaches “A method and apparatus for controlling and providing force feedback using an interface device manipulated by a user. A microprocessor is provided local to the interface device and reads sensor data from sensors that describes the position and/or other information about an object grasped and moved by the user, such as a joystick. The microprocessor provides the sensor data to a host computer that is coupled to the interface device by a communication bus that preferably includes a serial interface. In a “host-controlled” embodiment, the host computer calculates force values using the sensor data and other parameters of a host application program and sends the force values to the local microprocessor, which directly provides the force values to actuators to apply forces to the user object. In a “reflex” embodiment, the host computer sends high level supervisory commands to the local microprocessor, and the microprocessor independently implements a local process based on the high level command for reading sensor data and providing force values to the actuators using sensor data and other parameters.”
U.S. Published Patent Application No. 2005/0046629, entitled “Animation method of deformable objects using an oriented material point and generalized spring model,” that was published by Jeong et al. teaches “Disclosed is an animation method of deformable objects using an oriented material point and generalized spring model. The animation method comprises the following steps of: modeling a structure of a deformable object into oriented material points and generalized springs; initializing forces and torques acting on the material points, calculating the forces acting on the material points owing to collision of the material points and gravity, calculating the spring forces and torques acting on the material points, obtaining new positions and postures of the material points; updating positions, velocities, postures and angular velocities of the material points based upon physics, and displaying and storing updated results. The oriented material point and generalized spring model of the invention contains the principle of the conventional mass-spring model, but can animate deformable objects or express their structures in more intuitive manner over the conventional mass-spring model. Also, the material point and generalized spring model of the invention can express elongate deformable objects such as hair and wrinkled cloth, which cannot be expressed in the prior art, so as to animate features of various objects.”
U.S. Published Patent Application No. 2003/0088389, entitled “Long elements method for simulation of deformable objects,” that was published by Balaniuk et al. teaches “Long Elements Method (LEM) for real time physically based dynamic simulation of deformable objects. The LEM is based on a new meshing strategy using long elements whose forms can be straight or arbitrary. The LEM implements a static solution for elastic global deformations of objects filled with fluid based on the Pascal's principle and volume conservation. The volumes are discretised in long elements, defining meshes one order of magnitude smaller than meshes based on tetrahedral or cubic elements. The LEM further combines static and dynamic approaches to simulate the same deformable medium, allowing modeling a three-dimensional internal state at any point inside the deforming medium from a reduced number of explicitly updated elements. Complex elastic and plastic deformations can be simulated in real time with less computational effort. The LEM is particularly useful in real time virtual interactions, soft tissue modeling, and graphic and haptic rendering.”
U.S. Published Patent Application No. 2002/0180739, entitled “Method and apparatus for simulating soft object movement” that was published by Reynolds et al. teaches “Movement of a soft body is simulated by defining its surface as an arbitrary mesh of points connected by edges. Each point is represented as a point mass, subject to conventional laws of motion. The simulator represents forces acting on the point masses, namely skin forces connecting pairs of point masses and volumetric forces for maintaining relative positions with no net linear or rotational forces on the soft body.”
In a paper entitled “Virtual Reality Vitrectomy Simulator,” published by Paul F. Neumann, Lewis L. Sadler, and Jon Gieser M.D. in the Proceedings of the First International Conference on Medical Image Computing and Computer-Assisted Intervention, 1998, pp. 910-917 teaches “In this study, a virtual reality vitrectomy simulator is being developed to assist Ophthalmology residents in correcting retinal detachments. To simulate this type of surgery, a three dimensional computer eye model was constructed and coupled with a mass-spring system for elastic deformations. Five surgical instruments are simulated including: a pick, blade, suction cutter, laser, and drainage needle. The simulator will be evaluated by a group of fellows and retinal surgeons with a subjective Cooper-Harper survey commonly used for flight simulators.”
In an IEEE paper entitled “Deformable models: physical based models with rigid and deformable components,” published by Demetri Terzopoulous and Andrew Witkin, in IEEE Computer Graphics and Applications, November 1988, pp. 41-51 teaches “This article develops an alternative formulation of deformable models. We decompose deformations into a reference component, which may represent an arbitrary shape, and a displacement component allowing deformation away from this reference shape. The reference component evolves according to the laws of rigid-body dynamics. Equations of nonrigid motion based on linear elasticity govern the dynamics of the displacement component. With nonrigid and rigid dynamics operating in unison, this hybrid formulation yields well-conditioned discrete equations, even for complicated reference shapes, particularly as the rigidity of models is increased beyond the stability limits of our prior formulation. We illustrate the application of or deformable models to a physically based computer animation project.”
Thus, it is desirable to have a general-purpose interactive material simulation that solves most or all of the problems discussed above.